程式、演算法與資料結構

剛開始接觸資料結構時，可以先記住一句話：**「程式是由演算法和資料結構組成的。」**這句話看起來有點抽象，其實意思很簡單。演算法負責決定問題要怎麼解決，資料結構則負責安排資料要怎麼存放，兩者配合起來，才能寫出一個完整的程式。

例如，要計算一到一百的總和，我們可以用迴圈把每個數字依序加起來：

#include <stdio.h>

int main(void) {
    int n = 100;
    int sum = 0;

    for (int i = 1; i <= n; i++) {
        sum += i;
    }

    printf("1 到 %d 的總和是 %d\n", n, sum);

    return 0;
}

這段程式中的迴圈和加總步驟，就是演算法的一部分。簡單來說，演算法是一套用來解決問題的明確步驟。一個完整的演算法通常可以從以下五個重點來理解：

1. 輸入（Input）：演算法可以接收零個或多個輸入，這些輸入就是處理問題時需要的資料。例如，計算兩個數字的總和時，兩個數字就是輸入。前面的程式沒有讓使用者輸入資料，而是直接在程式中設定 n = 100，所以執行時不需要外部輸入。
2. 輸出（Output）：演算法至少要產生一個可以辨識的結果。例如，一到一百的加總結果是 5050，程式會利用 printf() 將它顯示出來，這就是輸出。
3. 明確性（Definiteness）：每一個步驟都必須寫得清楚，不能讓執行者有不同的解讀。例如，sum += i 明確表示要把目前的 i 加進 sum；如果只寫「把數字適當地加起來」，就不知道實際應該怎麼做，不算是明確的步驟。
4. 有限性（Finiteness）：演算法必須在有限的步驟內結束，不能無止境地執行。前面的迴圈從 i = 1 開始，每次將 i 加一，當 i 大於 100 時就會停止，因此它一定能結束。如果忘記更新 i，迴圈就可能一直執行，形成無窮迴圈。
5. 有效性（Effectiveness）：演算法中的每一個步驟都必須足夠基本，而且是實際可以執行的。例如，加法、比較大小和將變數加一，都是電腦能直接完成的基本操作；如果某個步驟寫成「立刻找出所有問題的最佳答案」，卻沒有說明具體做法，就不具備有效性。

因此，在這個例子中，程式先設定要加總到 100，再用迴圈反覆執行明確的加法，最後輸出總和 5050。整個過程有清楚的步驟，也能在有限時間內完成，所以可以視為一個完整的演算法。

資料抽象化與抽象資料型態

知道演算法是什麼之後，接著要分清楚資料型態和資料結構。資料型態是在描述一個變數可以存放哪一類資料，例如 int 用來存整數、float 用來存小數、char 用來存字元。資料結構考慮的則是多筆資料要怎麼組織，才能方便程式存取與處理。例如，陣列會把多個相同型態的元素依照順序排列在一起，是一種常見的基礎資料結構。

從廣義來看，資料結構可以視為資料抽象化的結果。所謂抽象化，就是先把許多細節整理起來，再用一個比較容易溝通的名稱代表它。以「飛機」為例，實際上它包含座椅、機翼、引擎和操縱系統，也具備起飛、轉向和降落等功能。不過平常溝通時，我們不需要每次都把所有零件和功能說一遍，只要說「飛機」，對方大致上就能理解我們指的是什麼。

資料的抽象化也有類似的概念，一方面要定義資料有哪些內容，以及這些內容要如何組織；另一方面還要定義可以對資料進行哪些操作。換句話說，資料結構不只是在說「資料擺成什麼形狀」，也包含這種排列方式能夠怎麼被使用。

不過，使用抽象名稱有一個前提，就是溝通雙方必須對這個名稱有相近的理解。假設有人只知道現實世界中的樹，第一次聽到「二元搜尋樹」時，腦中可能會浮現一棵植物；學過資料結構的人，想到的則會是由節點組成、具有特定排列規則的結構。這也是學習資料結構時必須熟悉專有名詞的原因。當我們了解陣列、鏈結串列、堆疊、佇列、樹和圖各自代表什麼，後續討論問題時才不容易各說各話。

使用 C 語言認識資料結構

那為什麼常用 C 語言來學習資料結構呢？因為 C 語言比較接近電腦底層，可以讓我們清楚看到資料在記憶體中如何存放，也比較容易理解陣列、指標和結構的實際運作方式。雖然剛開始可能會覺得 C 語言需要處理的細節很多，但這些細節能幫助我們建立扎實的程式設計基礎。

依照這份筆記採用的分類，程式語言對資料抽象化的支援可以分成三個層次。第一層是基礎型資料型態，例如整數、浮點數和字元；第二層是結構型資料型態，例如陣列和結構；第三層則是抽象資料型態（ADT）。ADT 不只描述資料如何組成，還會一起規定可以對資料進行哪些操作。

這三個層次可以用下面的例子來理解：

1. 基礎型資料型態：像 int age = 18;，只用一個變數保存一筆整數資料。
2. 結構型資料型態：像 int scores[3] = {80, 90, 70};，利用陣列把三筆相同型態的成績依序組織在一起。
3. 抽象資料型態（ADT）：像「堆疊」會規定資料必須後進先出，並提供 push（放入）、pop（取出）等操作。使用者只需要知道怎麼操作，不一定要知道內部是以陣列還是鏈結串列實作。

C 語言主要直接提供基礎型與結構型資料型態，所以我們常利用陣列和 struct 組織資料，再另外撰寫函式完成相關操作。雖然 C 語言沒有類別，但仍然可以透過 struct 搭配函式來實作 ADT。物件導向語言則可以利用類別，把資料和相關操作包在一起，隱藏更多實作細節。C 語言需要我們親自處理較多細節，因此也更容易看清楚一個資料結構是怎麼建立與運作的。

除了基本資料型態之外，C 語言也可以使用 struct，把多個彼此相關、但型態不同的資料組合在一起。假設我們想記錄一位學生的姓名和年齡，就可以這樣寫：

struct Student {
    char name[20];
    int age;
};

這裡的 struct Student 是一種自訂資料型態，它讓姓名和年齡可以被當成同一份學生資料來使用。它和物件導向語言中的物件有點相似，但兩者並不相同。C 語言的 struct 主要負責組合資料，相關操作通常要另外寫成函式；物件導向語言的類別則可以同時包含資料和操作資料的方法。

如果要記錄五位學生的姓名和成績，還可以把 struct 和陣列放在一起使用：

#include <stdio.h>

struct Student {
    char name[20];
    float score;
};

int main(void) {
    struct Student students[5];
    float total = 0.0f;
    float average;

    // 輸入五位同學的資料
    for (int i = 0; i < 5; i++) {
        printf("請輸入第 %d 位同學姓名：", i + 1);
        scanf("%19s", students[i].name);

        printf("請輸入成績：");
        scanf("%f", &students[i].score);

        total += students[i].score;
    }

    average = total / 5;

    printf("\n五位同學的資料：\n");
    for (int i = 0; i < 5; i++) {
        printf("%s：%.2f 分\n",
               students[i].name,
               students[i].score);
    }

    printf("\n平均成績：%.2f 分\n", average);

    return 0;
}

在這個例子裡，struct Student 定義了一位學生需要哪些資料，students[5] 則用陣列保存五位學生。這部分是在安排資料的結構。至於輸入學生資料、累加成績、計算平均和輸出結果的步驟，則屬於演算法。光是一個計算平均成績的小程式，就能看出資料結構和演算法是怎麼互相配合的。

如果接著要把學生依照成績排序，我們就需要再設計排序演算法。排序方法可能有很多種，但它們都會操作同一批學生資料。如果改變資料的儲存方式，相關演算法通常也要跟著調整。因此，選擇合適的資料結構，不但會影響程式的執行效率，也會影響程式是否容易維護。

小結

學習資料結構，是為了讓我們能根據不同問題，選擇合適的方式來組織與處理資料。選對資料結構，不但能提升程式的執行效率，也能讓程式更清楚、更容易維護。